class Solution(object):
    def snakesAndLadders(self, board):
        n = len(board)
        p = [-1] * (n ** 2 + 1)
        p[1] = 0
        def convert(value):
            i = (value - 1) // n
            j = (value - 1) % n
            if i % 2 == 0:
                return n - 1 - i, j
            else:
                return n - 1 - i, n - 1 - j
        now = {1}
        dist = 0
        while now:
            dist += 1
            next_set = set()
            for node in now:
                for next_node in range(node + 1, min(node + 7, n ** 2 + 1)):
                    x, y = convert(next_node)
                    if board[x][y] != -1:
                        next_node = board[x][y]
                    if p[next_node] == -1 or p[next_node] > dist:
                        p[next_node] = dist
                        next_set.add(next_node)
            now = next_set
        return p[-1]





data = Solution()
board = [[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [-1, 35, -1, -1, 13, -1],
         [-1, -1, -1, -1, -1, -1], [-1, 15, -1, -1, -1, -1]]
print(data.snakesAndLadders(board))
